#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/8/30 16:20
# @USER    : Shengji He
# @File    : PartitionList.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:


# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def partition(self, head: ListNode, x: int) -> ListNode:
        """
        Given a linked list and a value x, partition it such that all nodes less than x come before nodes
        greater than or equal to x.

        You should preserve the original relative order of the nodes in each of the two partitions.

        Example:
            Input: head = 1->4->3->2->5->2, x = 3
            Output: 1->2->2->4->3->5

        :param head:
        :param x:
        :return:
        """
        before = before_head = ListNode(0)
        after = after_head = ListNode(0)

        while head:
            if head.val < x:
                before.next = head
                before = before.next
            else:
                after.next = head
                after = after.next
            head = head.next

        after.next = None
        before.next = after_head.next
        return before_head.next


if __name__ == '__main__':
    S = Solution()
    head = ListNode(1)
    head.next = ListNode(4)
    head.next.next = ListNode(3)
    head.next.next.next = ListNode(2)
    head.next.next.next.next = ListNode(5)
    head.next.next.next.next.next = ListNode(2)
    x = 3
    S.partition(head, x)
    print('done')
